package basic.datastruct.二叉树;

import java.util.*;

/**
 * @创建人 MBY381
 * @创建时间 2022/4/19 20:43
 * @描述 暂无
 */
public class ZigzagPrint {
    public static void main(String[] args) {
        TreeNode node1=new TreeNode(1);
        TreeNode n2=new TreeNode(2);
        TreeNode n3 =new TreeNode(3);
        TreeNode n4 =new TreeNode(4);
        TreeNode n5 =new TreeNode(5);
        node1.left=n2;
        node1.right=n3;
        n2.left=n4;
        n3.right=n5;
        System.out.println(zigzagPrint(node1));
    }
    public static List<List<Integer>> zigzagPrint(TreeNode root){
        List<List<Integer>> ans=new ArrayList<>();
        if(root==null){
            return ans;
        }
        Queue<TreeNode> queue=new ArrayDeque<>();
        queue.add(root);
        int index=0;
        while(!queue.isEmpty()){
            List<Integer> li=new ArrayList<>();
            int len=queue.size();
            for(int i=0;i<len;i++){
                TreeNode node=queue.poll();
                if(index%2==1){
                    li.add(Objects.requireNonNull(node).val);
                }else {
                    li.add(0, Objects.requireNonNull(node).val);
                }
                index++;
                if(node.left!=null){
                    queue.add(node.left);
                }
                if(node.right!=null){
                    queue.add(node.right);
                }
            }
            ans.add(li);
        }
        return ans;
    }
}
